\chapter{Protocolo \textit{Token Ring} sem fio}
\label{cap:referencia}

Nas próximas seções, faremos uma revisão do protocolo \textit{Token Ring} sem fio (WTRP)
\cite{ergenthesis}.

Primeira versão de WTRP foi desenvolvida por uma equipe de 
pesquisadores da \textit{Berkeley}~\cite{lee_original} liderada pelo Dr. Duke Lee. O objetivo 
era apresentar uma solução para sistemas de transportes inteligentes. Sucederam outras versões
~\cite{lee_second} no sentido de melhorar o protocolo. Dentre as versões posteriores Dr. Mustafa
Ergen produziu a versão que serve de base para o nosso trabalho.

\section{Definições}
 Os termos (e as suas definições) no \cite{ergenthesis} que consideramos relevantes para o nosso
trabalho são:
 \begin{enumerate}
  \item quadro refere a sequência de bits que é passada a camada fisica.
  \item um nó representa qualquer dispositivo móvel, capaz de detectar, receber e transmitir sinais.
 As palavras estação e nó são usados como sinônimos (não só neste capítulo, mas em todo o trabalho).
  \item predecessor e sucessor de um nó X representam os nós de quem X recebe, e a quem
 o X passa um \textit{token}, respectivamente.
  \item ``anel próprio'' refere a um anel onde os campos sucessor e predecessor de qualquer nó são
identificadores (ID) corretos (\textit{vide} o trabalho~\cite{ergenthesis} seção 1 do capítulo 10).
  \item a capacidade de uma rede é o total da sua largura de banda.
  \item Um \textit{token} é uma sequência de sinal transmitido de nó em nó usado para controlar
  o acesso a meio~\cite{trspec}. O ``\textit{token}'' e ``\textit{token} de permissão'' serão usados
   indiscriminadamente.
 \end{enumerate}


\section{Revisão de arquitetura de sistema}
\label{sec:arquitetura}

\subsection{Controle de acesso ao meio}
Controle de acesso ao meio (MAC) permite várias estações transmitirem no mesmo meio (canal). 
Mas também é possível utilizar múltiplos canais de forma a reduzir colisões (falaremos 
desse assunto mais adiante).

Na arquitetura de WTRP, a camada MAC gerencia um anel e tempo de transmissões neste anel.

O gerenciamento de um anel envolve:
\begin{enumerate}
 \item Certificar que cada anel (podemos ter vários anéis isolados) tem um único endereço.
 \item Certificar que existe exatamente um \textit{token} para um anel.
 \item Certificar que o anel é próprio.
 \item Executar operações de inclusão e saída de estações.
\end{enumerate}

\subsection{Alocador de canal}
 Alocador de canal escolhe um canal em que um nó deve transmitir de modo a evitar interferências.
 No WTRP, cada estação (nó) possui um alocador de canal. Então, cada nó tem capacidade
 de decidir que canal usar (de forma distribuída) analizando as informações coletadas de \textit{token}.
 Um \textit{token} contém um campo designado a número de nós (NoN) em anel.
 Se esse NoN alcançar o valor máximo, então é uma indicação que estações fora do anel
 não podem aderir a este anel. Consequentemente, esses nós devem buscar outros anéis.


\subsection{Gerenciador de mobilidade}
 Gerenciador de mobilidade decide quando uma estação entra ou sai do anel. O problema
 que o gerenciador de mobilidade tem a resolver é similar ao problema de \textit{hand-off}
 móvel. I.e., quando um nó móvel se afasta de um anel e se aproxima de um outro anel, por um limiar,
 o gerenciador de mobilidade decide mudar este nó para o anel a qual ele se aproxima.


\subsection{Controle de admissão}
 Controlador de admissão tem a responsabilidade de limitar o número de estações que podem
 transmitir em um meio. Isso assegura latência limitada e largura de banda reservada para
estações que já têm permissão para transmitir no meio. Existe um controlador de admissão em 
cada anel. O controlador de admissão pode mover com o \textit{token}, mas não tem que mover
sempre que o \textit{token} move. Periodicamente, ele solicita outras estações para participarem
do anel, se algum recurso está disponível. E, somente estações que precisam de menos recursos
que o disponíveis podem tentar participar do anel \cite{ergenjournal}.


\section{O protocolo \textit{Token Ring} sem fio}
\label{sec:protocolo}


\subsection{Descrição}
Em WTRP, os campos predecessor e sucessor de cada nó definem o anel e a ordem de transmissão.

Uma estação recebe \textit{token} do seu predecessor, transmite dados e passa o \textit{token} para o seu sucessor. A seguir, 
ilustraremos um quadro de \textit{token} e passamos a explicar os campos incluídos nele:
\begin{table}[!hc]
\centering
		\begin{tabular}[c]{|c|c|c|c|c|c|c|c|} 
			\hline 
			FC & RA & DA & SA & NoN & Gen\_Seq & Seq\\ 
			\hline
		\end{tabular}
           \caption{Quadro de \textit{Token} \cite{ergenthesis}}
\label{tab:quadrotoken}
\end{table}
O campo FC designa tipo de pacote, tais como \textit{Token} de permissão (o \textit{token} tradicional), \textit{Solicit Successor,
Set Predecessor, etc}. Os campos endereço de origem (SA), endereço destino (DA), endereço de anel (RA), número de sequência (Seq),
e o número de geração são incluídos. RA designa o anel a que o \textit{token} pertence. Seq é inicializado com zero
e é incremetado por cada nó que recebe o \textit{token}. Gen\_Seq é inicializado com zero e incrementado cada
vez que o proprietário de anel recebe o \textit{token}. Também, NoN é representado no anel, ele é calculado
através de diferença de Seq em uma rotação do \textit{token}.

Cada nó mantém informações sobre as transmissões feitas no seu anel e nos anéis próximos. Para ajudar nessa tarefa,
cada nó constrói e mantém localmente uma lista ordenada de nós no seu anel e uma lista não ordenada e global
de nós fora do seu anel. Na figura 3.1, a estação D monitora

%DESENHO AQUI E AS SUAS EXPLICAÇÕES
\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{tabelaconectividade-ref.pdf}
\caption{Tabela de conectividade \cite{ergenthesis}}
\label{fig:tabeladeconectividade}
\end{figure}
\noindent as sucessivas transmissões de \textit{token} de E para F antes que o \textit{token} volte a ele. No tempo 0, D transmite o
\textit{token} com sequência número 0; no tempo 1, E transmite o \textit{token} com sequência 1, e assim a diante. D
não escutará as transmissões de F e A, mas quando ele escutar transmissão de origem no B,
D reparará que o número de sequência foi aumentado em 3 ao invés de 1. Isso indica a D que
houveram duas estações que ela não conseguiu escutar entre E e B.

Proprietário de um anel é a estação cujo endereço MAC é o mesmo que o endereço de anel. Proprietário
de um anel pode mudar. Para isso, basta o nó reivindicador mudar o endereço de anel para o seu
endereço MAC.

Um nó depende de \emph{ACK} implícito (\emph{AckI}) para monitorar a sua transmissão de \textit{token}.
Quando ele receber \emph{AckI}, o nó fica ciente que a sua transmissão de \textit{token} foi bem sucedida.
Ou seja, se nenhum \emph{AckI} for escutado então o \textit{token} não terá sido recebido e
se perdeu. Neste caso, o tempo de espera pela transmissão de \textit{token} expirou. Como consequência, o nó
que não escutou o \emph{AckI} gerará um novo \textit{token} e auto proclamar-se-á proprietário do \textit{token}.

%RESOLUÇÃO DE MULTIPLOS TOKEN
Para resolver problema de vários \textit{token}s (eliminar todos exceto um), um conceito de prioridade
é usado. Gen\_Seq e RA definem a prioridade de um \textit{token}. Um \textit{token} com Gen\_Seq maior tem prioridade
mais alta. Quando Gen\_Seq de dois \textit{token}s são iguais, endereço de anel de cada \textit{token} é usado
para o desempate. A prioridade de um nó é a prioridade do último \textit{token} que este nó aceitou ou gerou.
Quando um nó recebe um \textit{token} com prioridade menor que a dele, ele elimina o \textit{token} e notifica
o predecessor sem aceitar o \textit{token}. %Este esquema mostra que o protocolo pode eliminar múltiplo \textit{token}s
%em uma rotação............

O mecanismo de recuperação de anel é invocado quando o nó que faz monitoramento decide que o seu
sucessor não está alcançável. Neste caso, o nó tenta recuperar da falha formando anel novamente.
A estratégia de WTRP para reconstruir um anel é tentar excluir o menor número possível de nós.
Usando a tabela de conectividade, o nó que faz monitoramento é capaz de rapidamente encontrar
(na ordem de transmissão) um nó (no anel) para reconectar o anel enviando uma mensagem de reconexão
para o nó escolhido.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.5]{joining-ref.pdf}
\caption{Procedimento de entrada \cite{ergenthesis}}
\label{fig:referenciaentrada}
\end{figure}

WTRP permite nós aderirem a um anel dinamicamente, um por vez, se o tempo de rotação de \textit{token} (soma de tempos
THT por nó, mais \textit{overhead} tal como tempos de transmissão de \textit{token}) não cresça inaceitavelmente
com a adição de novo nó. Suponha que nó B deseja aderir ao anel (figura \ref{fig:referenciaentrada}).
Digamos também que A faz \textit{broadcast} (Br) da mensagem ``Solicitar sucessor'' (que inclui sucessor
C de A) para que outros nós possam aderir ao anel. O controlador de admissão no nó A espera pelas respostas 
de nós interessados por algum tempo antes de decidir qual candidato incluir. Por sua vez, um nó que queira ser incluso no anel,
por exemplo B, quando escutar a mensagem ``Solicitar sucessor'', ele transmite uma mensagem 
``Atribuir sucessor'' para o nó A. Quando o tempo de espera pelas respostas terminar, o nó A pode decidir quem é
o vencedor. Suponha que B vença a contenda, então o nó A passa para B a mensagem ``Atribuir predecessor'',
e B passa para nó C a mensagem ``Atribuir predecessor''. Assim, termina o procedimento de entrada.


\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{exiting-ref.pdf}
\caption{Procedimento de saida \cite{ergenthesis}}
\label{fig:referenciasaida}
\end{figure}

Como mostra a figura \ref{fig:referenciasaida}, suponhamos que estação B queira deixar o anel. Primeiro,
B espera chegar a sua vez de transmitir. Uma vez que tenha chegado, B envia um pacote ``Atribuir predecessor''
com endereço MAC do sucessor de B (no caso, nó C) para o predecessor A. Se A consegue
escutar C, ele tenta conectar com C enviando um pacote ``Atribuir predecessor''. Se A não consegue 
escutar C, ele buscará (na ordem de transmissão) um nó na tabela de conectividade e que está no mesmo anel,
e envia um pacote ``Atribuir predecessor'' a esse nó.

O protocolo WTRP implementa eliminação de interferências. Para isso, um nó pode ser incluso em qualquer anel
se e somente se o anel não atingiu a capacidade máxima (em número de nós - NoN). Esse número máximo de nós
é global a todos os anéis. Quando um nó deseja fazer parte de um anel, se ele detectar um \textit{token},
verifica se tem vaga. Se não tiver, ele continuará buscando por um anel (através de \textit{token} detectado)
que ainda tenha vaga. Se o anel detectado ainda tiver vaga, o nó que deseja fazer parte do anel pode aguardar
por uma mensagem ``Solicitar sucessor'' transmitida por um nó no anel.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{m-ring-ref.pdf}
\caption{Vários anéis \cite{ergenthesis}}
\label{fig:variosaneis}
\end{figure}

Na figura \ref{fig:variosaneis}, podemos ver que o endereço de qualquer anel é sempre o endereço de
algum nó nesse anel. Este nó é chamado de proprietário do anel. No exemplo, o proprietário do anel
A é o nó A. Uma vez que supomos que o endereço MAC de um nó é único então endereço de um anel
também é único. Esta unicidade de endereço é importante, uma vez que permite a nós distinguirem
mensagens vindas de diferentes anéis. <<O nosso projeto propõe estudo e implementação 
para múltiplos anéis.>>

Para assegurar que um proprietário está presente em um anel, ele atualiza o Gen\_Seq cada vez que
receber um \textit{token}. Quando o proprietário deixa o anel, o sucessor dele vai alterar predecessor,
e ficar ciente que endereço do anel não é igual ao identificador do seu predecessor, então
ele pode assumir papel de proprietário do anel.
Também, caso um proprietário deixe anel dele sem notificar às estações restantes no anel. Nesse caso,
para concluir que o proprietário está inalcançável, basta alguma estação receber o \textit{token}
com valor de Gen\_Seq desatualizado.

\section{Outros trabalhos relacionados}
\label{sec:outrosrelacionados}
Vários outros trabalhos foram feitos com foco em \textit{Token Ring} sem fio. Na verdade, esse
protocolo foi inicialmente introduzido pela equipe da Universidade de Califórnia \textit{Berkeley}
liderada por Duke Lee como parte dos projetos de Sistema de transportação inteligente, e aeronaves
não tripuladas~\cite{lee_original, lee_second}. Ainda, Top \textit{et} al. apresentam uma versão de WTRP
para uso em ambientes dinâmicos \textit{ad-hoc}~\cite{top}; em~\cite{cheng}, uma versão extendida capaz de permitir
várias transmissões em simultâneo em WMAN (Rede de área metropolitana sem fio); em~\cite{deng}, Deng \textit{et} al.
analisam o desempenho de WTRP e propõem uma versão com foco em reduzir consumo de energia; e ainda, em~\cite{deng_2},
Deng \textit{et} al. propõem uma versão de WTRP de pequena escala com mecanismo de preempção, hibernação e contenção.

Também, para pesquisas em tolerância a falha, controle de acesso ao meio, desafios em redes \textit{ad-hoc} sem fio,
estudo de QoS em termos de filas de armazenamento de pacotes em redes sem fio consultamos~\cite{kurose, lauf, kawahigashi,
casale, jun, llewellyn}.
